package cn.cxq.learning.tree;


import org.junit.jupiter.api.Test;

import java.math.BigInteger;

/**
 * 牛客题霸-算法篇
 * 二叉树的个数
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M 热度指数：680
 * 本题知识点： 树
 *  算法知识视频讲解
 * 题目描述
 * 已知一棵节点个数为n的二叉树的中序遍历单调递增，求该二叉树能能有多少种树形,输出答案取模10^9+710
 * 9
 *  +7
 * 示例1
 * 输入
 * 复制
 * 2
 * 返回值
 * 复制
 * 2
 * 示例2
 * 输入
 * 复制
 * 1
 * 返回值
 * 复制
 * 1
 */
public class NumOfBinaryTree {

    @Test
    public void test() {
        System.out.println(numberOfTree(100000));
    }

    // 超时。。。 等待优化解决
    public int numberOfTree(int n) {
        BigInteger ans = BigInteger.ONE;
        BigInteger four = BigInteger.valueOf(4);
        BigInteger two = BigInteger.valueOf(2);
        BigInteger one = BigInteger.ONE;
        BigInteger mod = BigInteger.valueOf(1000000007);

        for (int i = 1; i <= n; i++) {
            BigInteger bi = BigInteger.valueOf(i);
            ans = ans.multiply(four.multiply(bi).subtract(two)).divide(bi.add(one));
        }

        return Integer.parseInt(ans.mod(mod).toString());
    }

    @Test
    public void testCatalanNumber() {
        // 打印前 n 个卡特兰数
        int n = 20;
        BigInteger ans = BigInteger.valueOf(1);
        System.out.println("1:" + ans.toString());
        BigInteger four = BigInteger.valueOf(4);
        BigInteger one = BigInteger.valueOf(1);
        BigInteger two = BigInteger.valueOf(2);
        for (int i = 2; i <= n; i++) {
            BigInteger bi = BigInteger.valueOf(i);
            ans = ans.multiply(four.multiply(bi).subtract(two)).divide(bi.add(one));
            System.out.println(i + ":" + ans.toString());
        }
    }
}
